package 剑指offer.链表;

/**
 * 输入两个链表，链表相交。找出他们的公共节点
 */
public class 第52题两个链表的第一个公共节点 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 先找出两个链表的长度，计算长度差 K
     * 然后长的先走K步，然后两个链表再同时往下走，第一次相遇时就是交点
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null)
            return null;
        int size1 = 0;
        ListNode p1 = pHead1;
        while (p1 != null) {
            size1++;
            p1 = p1.next;
        }
        int size2 = 0;
        ListNode p2 = pHead2;
        while (p2 != null) {
            size2++;
            p2 = p2.next;
        }
        // 先统计 pHead1 和 pHead2 的长度，让最长的先走几步，好让他们从同样的长度开始往下走
        int lengthDiff = size1 >= size2 ? size1 - size2 : size2 - size1;
        if (size1 >= size2) {
            while (lengthDiff != 0) {
                pHead1 = pHead1.next;
                lengthDiff--;
            }
        } else {
            while (lengthDiff != 0) {
                pHead2=pHead2.next;
                lengthDiff--;
            }
        }
        // 一边走一遍比较是否遇到相同的值
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val == pHead2.val) {
                return pHead1;
            } else {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return null;
    }

}
